1. Field of the Invention
The present invention relates to an adder circuit, and more particularly, it relates to an adder provided with carry look ahead circuits.
2. Description of the Background Art
FIG. 8 is a block diagram showing the structure of a conventional adder circuit for adding two 16-bit data to each other.
The first 16-bit data is formed by data A0 to A15, while the second 16-bit data is formed by data B0 to B15. This adder circuit includes 16 full adders 1 to 16 corresponding to the data A0 to A15 and B0 to B15, and four carry look ahead circuits 20 to 23.
The full adders 1 to 16 are supplied with the data A0 to A15 and B0 to B15 in data input terminals A and B thereof respectively. The 16 full adders 1 to 16 are classified into four groups, so that each group is provided with one of the carry look ahead circuits.
A carry input terminal CI of the full adder 1 and a propagation carry input terminal Cp of the carry look ahead circuit 20 are connected to a least significant carry input terminal CL. Carry input terminals CI of the full adders 2, 3 and 4 are connected to carry output terminals CO of the full adders 1, 2 and 3 provided on the low order sides respectively. A carry output terminal CO of the full adder 4 is connected to a generation carry input terminal CG of the carry look ahead circuit 20. Propagation detecting terminals P of the full adders 1, 2, 3 and 4 are connected to propagation detecting input terminals P0, P1, P2 and P3 of the carry look ahead circuit 20 respectively. The least significant carry input terminal CL is grounded.
Similarly to the above, full adders 5, 6, 7 and 8 are connected to a carry look ahead circuit 21, full adders 9, 10, 11 and 12 are connected to a carry look ahead circuit 22, and full adders 13, 14, 15 and 16 are connected to a carry look ahead circuit 23.
A carry input terminal CI of the full adder 5 and a propagation carry input terminal Cp of the carry look ahead circuit 21 are connected to a carry output terminal Co of the carry look ahead circuit 20. A carry input terminal CI of the full adder 9 and a propagation carry input terminal Cp of the carry look ahead circuit 22 are connected to a carry output terminal Co of the carry look ahead circuit 21. A carry input terminal CI of the full adder 13 and a propagation carry input terminal Cp of the carry look ahead circuit 23 are connected to a carry output terminal Co of the carry look ahead circuit 22. A carry output terminal Co of the carry look ahead circuit 23 is connected to a most significant carry output terminal CM.
Sum signals SO to S15 are outputted from sum signal output terminals S of the full adders 1 to 16 respectively. These sum signals SO to S15 form a 16-bit data expressing the sum of the first and second 16-bit data.
FIG. 9 shows a block diagram illustrating a single full adder and a circuit diagram illustrating an exemplary structure of the full adder at (a) and (b) respectively. FIG. 10 illustrates the truth table of the full adder shown in FIG. 9.
The full adder shown in FIG. 9 includes an exclusive OR gate 33, inverters 34 and 35, and transfer gates 36, 37, 38 and 39. A data input terminal A is supplied with one bit of a binary data, while another data input terminal B is supplied with one bit of another binary data. A carry input terminal CI is supplied with a carry signal which is outputted from a full adder provided on a low order side.
A signal at a propagation detecting terminal P expresses exclusive OR of the data received in the data input terminals A and B. Namely, the signal at the propagation detecting terminal P is "1" when the data received in the data input terminal A is different from that received in the data input terminal B, while this signal is "0" when the former is identical to the latter.
When the signal at the propagation detecting terminal P is "1", the transfer gates 37 and 39 are turned on and the transfer gates 36 and 38 are turned off. Thus, an inversion signal of the carry signal received in the carry input terminal CI is propagated to a sum signal output terminal S, while the carry signal received in the input terminal CI is propagated to a carry output terminal CO.
When the signal at the propagation detecting terminal P is "0", on the other hand, the transfer gates 36 and 38 are turned on and the transfer gates 37 and 39 are turned off. Therefore, the carry signal received in the carry input terminal CI is propagated to the sum signal output terminal S, while the data received in the data input terminal B is propagated to the carry output terminal CO.
As shown in FIG. 10, the signal at the propagation detecting terminal P is "0" when both of the data received in the data input terminals A and B are "0". Thus, the carry signal received in the carry input terminal CI is propagated to the sum signal output terminal S. When the carry signal received in the carry input terminal CI is "0", therefore, a sum signal at the sum signal output terminal S is also "0", while the sum signal at the sum signal output terminal S is "1" when the carry signal received in the carry input terminal CI is "1". The data received in the data input terminal B is propagated to the carry output terminal CO. Thus, the carry signal at the carry output terminal CO is "0". This state is called a kill state.
When both of the data received in the data input terminals A and B are "1", on the other hand, the signal at the propagation detecting terminal P is "0". Thus, the carry signal received in the carry input terminal CI is propagated to the sum signal output terminal S. When the carry signal received in the carry input terminal CI is "0", therefore, the sum signal at the sum signal output terminal S is also "0", while this signal is "1" when the carry signal received in the carry input terminal CI is "1". The data received in the data input terminal B is propagated to the carry output terminal CO. Thus, the carry signal at the carry output terminal CO is "1". This state is called a generation state.
When the data received in the data input terminals A and B are different from each other, the signal at the propagation detecting terminal P is "1". Thus, an inversion signal of the carry signal received in the carry input terminal CI is propagated to the sum signal output terminal S. When the carry signal received in the carry input terminal CI is "0", therefore, the sum signal at the sum signal output terminal S is "1", while this signal is "0" when the carry signal in the carry input terminal CI is "1". The carry signal received in the carry input terminal CI is propagated to the carry output terminal CO. When the carry signal received in the carry input terminal CI is "0", therefore, the carry signal at the carry output terminal CO is also "0", while this signal is "1" when the carry signal received in the carry input terminal CI is "1". This state is called a propagation state.
Thus, the carry signal at the carry output terminal CO is "0" in a kill state regardless of the state of the carry signal received in the carry input terminal CI. In a generation state, on the other hand, the carry signal at the carry output terminal CO is "1" regardless of the state of the carry signal received in the carry input terminal CI. In a propagation state, further, the carry signal received in the carry input terminal CI is propagated to the carry output terminal CO.
In the full adder shown in FIG. 9, the sum of the data received in the data input terminals A and B is obtained at the sum output terminal S as a sum signal and the carry signal is obtained at the carry output terminal CO on the basis of the data received in the data input terminals A and B and the carry signal received in the carry input terminal CI. When the carry signal is propagated from the carry input terminal CI to the carry output terminal CO, the signal (propagation detecting signal) at the propagation detecting terminal P is "1".
FIG. 11 shows a block diagram illustrating a single carry look ahead circuit and a circuit diagram illustrating an exemplary structure of the carry look ahead circuit at (a) and (b) respectively. FIG. 12 illustrates the truth table of the carry look ahead circuit shown in FIG. 11.
The carry look ahead circuit shown in FIG. 11 includes a NAND gate 26, an inverter 27 and transfer gates 28 and 29. Propagation detecting terminals P of four full adders are connected to propagation detecting input terminals P0, P1, P2 and P3 respectively. A generation carry input terminal CG is supplied with a carry signal which is outputted from one of the four full adders provided on the most significant bit side. A propagation carry input terminal Cp is supplied with a carry signal to be inputted in one of the four full adders provided on the least significant bit side.
When any of propagation detecting signals received in the propagation detecting input terminals P0, P1, P2 and P3 is "0", the transfer gate 28 is turned on and the transfer gate 29 is turned off. Thus, the carry signal received in the generation carry input terminal CG is propagated to a carry output terminal Co. When any of the full adders connected to this carry look ahead circuit is in a kill or generation state, therefore, the carry signal received in the generation carry input terminal CG is outputted from the carry output terminal Co.
When all propagation detecting signals received in the propagation detecting input terminals P0, P1, P2 and P3 are "1", on the other hand, the transfer gate 29 is turned on and the transfer gate 28 is turned off. Thus, the carry signal received in the propagation carry input terminal Cp is propagated to the carry output terminal Co. When all of the four full adders connected to this carry look ahead circuit are in propagation states, therefore, the carry signal received in the propagation carry input terminal Cp is outputted from the carry output terminal Co.
As shown in FIG. 12, the carry signal at the carry output terminal Co is equal to the carry signal received in the generation carry input terminal CG when the logical product of the propagation detecting signals received in the propagation detecting input terminals P0, P1, P2 and P3 is "0". When the logical product of the propagation detecting signals received in the propagation detecting input terminals P0, P1, P2 and P3 is "1", on the other hand, the carry signal at the carry output terminal Co is equal to the carry signal received in the propagation input terminal Cp.
As hereinabove described, the carry signal at the carry output terminal CO of each full adder is obtained by propagation of the carry signal received in the carry input terminal CI or the data received in the data input terminal B. Further, the sum signal at the sum signal output terminal S is obtained by propagation of the carry signal received in the carry input terminal CI or an inversion signal thereof.
Thus, the carry signal at the carry output terminal CO is delayed by a transfer gate with respect to the carry signal received in the carry input terminal CI or the data received in the data input terminal B. Further, the sum signal at the sum signal output terminal S is delayed by a transfer gate with respect to the carry signal received in the carry input terminal CI.
In each carry look ahead circuit, on the other hand, the carry signal at the carry output terminal Co is obtained by propagation of the carry signal received in the generation carry input terminal CG or that received in the propagation carry input terminal Cp.
Therefore, the carry signal at the carry output terminal Co is delayed by a transfer gate with respect to the carry signal received in the generation carry input terminal CG or that received in the propagation carry input terminal Cp.
In the adder circuit shown in FIG. 8, the time (delay time) required for obtaining all sum signals SO to S15 upon supply of the data A0 to A15 and B0 to B15 varies with the states of the full adders 1 to 16.
The maximum delay time is caused when the least significant bit full adder 1 is in a kill or generation state and the remaining full adders 2 to 15 are in propagation states.
In this case, a delay T1 is caused in the full adder 1 by propagation from the data input terminal B to the carry output terminal CO. In the full adder 2, a delay T2 is caused by propagation from the carry input terminal CI to the carry output terminal CO. Similarly, delays T3 and T4 are caused in the full adders 3 and 4 respectively.
Then, a delay T5 is caused in the carry look ahead circuit 20 by propagation from the generation carry input terminal CG to the carry output terminal Co. A delay T6 is caused in the carry look ahead circuit 21 by propagation from the propagation carry input terminal Cp to the carry output terminal Co, while a delay T7 is caused in the carry look ahead circuit 22 by propagation from the propagation carry input terminal Cp to the carry output terminal Co.
Further, a delay T8 is caused in the full adder 13 by propagation from the carry input terminal CI to the carry output terminal CO, while delays T9 and T10 are similarly caused in the full adders 14 and 15 respectively. Finally, a delay T11 is caused in the full adder 16 by propagation from the carry input terminal CI to the sum signal output terminal S.
Thus, a delay of 11 stages is caused before the sum signal S15 is obtained upon supply of the data A0 to A15 and B0 to B15.